/**
 * 53. 最大子数组和
 * https://leetcode-cn.com/problems/maximum-subarray/
 */

// /**
//  * 动态规划
//  * @param {number[]} nums
//  * @return {number}
//  */
// function maxSubArray(nums) {
//   const { length } = nums;
//   let max = nums[0];
//   let preMax = max;
//   for (let i = 1; i < length; i += 1) {
//     const cur = nums[i];
//     preMax = Math.max(preMax + cur, cur);
//     max = Math.max(preMax, max);
//   }
//   return max;
// }

/**
 * @param {number[]} nums
 * @param {number} begin
 * @param {number} end
 * @return {{ beginMax: number, endMax: number, centerMax: number, sum: number }}
 */
function dc(nums, begin, end) {
  if (begin === end) {
    const num = nums[begin];
    return {
      beginMax: num,
      endMax: num,
      centerMax: num,
      sum: num,
    };
  }
  const middle = Math.floor((begin + end) / 2);
  const {
    beginMax: leftBeginMax,
    endMax: leftEndMax,
    centerMax: leftCenterMax,
    sum: leftSum,
  } = dc(nums, begin, middle);
  const {
    beginMax: rightBeginMax,
    endMax: rightEndMax,
    centerMax: rightCenterMax,
    sum: rightSum,
  } = dc(nums, middle + 1, end);
  return {
    beginMax: Math.max(leftBeginMax, leftSum + rightBeginMax),
    endMax: Math.max(rightEndMax, rightSum + leftEndMax),
    centerMax: Math.max(leftCenterMax, rightCenterMax, leftEndMax + rightBeginMax),
    sum: leftSum + rightSum,
  };
}

/**
 * 分而治之
 * @param {number[]} nums
 * @return {number}
 */
function maxSubArray(nums) {
  const {
    beginMax, centerMax, endMax, sum,
  } = dc(nums, 0, nums.length - 1);
  return Math.max(beginMax, centerMax, endMax, sum);
}

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) === 6);
console.log(maxSubArray([1]) === 1);
console.log(maxSubArray([5, 4, -1, 7, 8]) === 23);
